﻿#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
/*
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。


示例 1 :

输入: g = [1, 2, 3], s = [1, 1]
	输出 : 1
	解释 :
	你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1, 2, 3。
	虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
	所以你应该输出1。
	示例 2 :

输入: g = [1, 2], s = [1, 2, 3]
	输出 : 2
	解释 :
	你有两个孩子和三块小饼干，2个孩子的胃口值分别是1, 2。
	你拥有的饼干数量和尺寸都足以让所有孩子满足。
	所以你应该输出2.
*/

//解题思路：以最小的为界限，逐渐比较

class Solution {
public:
	int findContentChildren(vector<int>& g, vector<int>& s) {
		std::sort(g.begin(), g.end());
		std::sort(s.begin(), s.end());
		int i = 0, j = 0;
		while (i < g.size() && j < s.size()) {
			if (g[i] <= s[j])
				++i;
			j++;
		}
		return i;
	}

	//当时想着是还要将已经吃掉的饼干删除掉, 并且不需要排序，但是如果出现相同，但是会出现小的吃了多的
	int findContentChildren_low(vector<int>& g, vector<int>& s) {
		std::sort(g.begin(), g.end());
		std::sort(s.begin(), s.end());
		vector<int> m;
		for (int i = 0; i < g.size(); ++i) {
			vector<int>::iterator itr = s.begin();
			for (; itr != s.end(); ++itr) {
				if (g[i] <= *itr) {
					m.push_back(*itr);
					itr = s.erase(itr);
					break;
				}
			}
		}
		return m.size();
	}
};